Public key encryption is an established technology invented in 1977 by Rivest, Shamir and Adleman [1], and is known as RSA. It is based on the considerable difficulty of factorizing large integers into prime factors. In RSA a large integer N which forms part of the public key is constructed from the product of two large prime numbers P1 and P2 which must be kept secret. An arbitrary integer e is chosen and the public key consists of N and e. The security of RSA is compromised if P1 and P2 are determined and this can be done, at least in theory, by factorising N. In typical implementations of RSA, N consists of a 1024 bit number which is predicted to be factorisable in practice within a few years with advances in computer technology. Longer numbers may be used such as 2048 bit numbers but alternative Public key systems based on different methods are likely to become more important.
One such public key system is the McEliece system [2] invented by the distinguished mathematician Robert McEliece in 1978 and it is based on the family of Goppa [3] error correcting codes and the difficulty of correcting unknown random errors if the particular Goppa code used in generating the public and private keys is unknown. A cleartext message is encoded into binary codewords using the public key and a randomly chosen error pattern containing up to t bits is added to each codeword. In decryption the associated private key is used to invoke an error correcting decoder based upon the underlying Goppa code to correct the errored bits in each codeword, prior to retrieval of the cleartext message.
In U.S. Pat. No. 5,054,066, Riek and McFarland improved the security of the system by complementing the error patterns so as to increase the number of errors contained in the cryptogram [4]. In GB1006747.8, published as GB2469393, Tjhai and Tomlinson (the present inventors) modified the original McEliece system and placed the emphasis on the error pattern so that the encryption system became semantically secure. Encrypting the same message using the same public key produces a completely different cryptogram with this system.
One of the criticisms of the McEliece system is that the public key is much larger than the corresponding RSA public key. There have been several attempts to modify the system using different error correcting codes so as to reduce the public key size such as that described by Berger et al [5] but in all cases the security of the system has been compromised.
One objective of the current invention is to reduce the public key size without compromising the security of the encryption system and to retain the family of Goppa error correcting codes as the basis of the encryption system. A further objective of the invention is to be able to exploit the implicit error correction capability so as to deal with naturally occurring errors in the transmission or retrieval of cryptograms, given the constraint of reduced public key size.